﻿#pragma once
#include "Index.h"

/**
 * 剑指 Offer 09. 用两个栈实现队列
 * https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/
 * 栈 设计 队列
 *
 * 用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，
 * 分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
 */
namespace TwoStackMakeQueue
{
    class Question
    {
    public:
        virtual void appendTail(int val) = 0;
        virtual int deleteHead() = 0;
    };

    class Monitor : public Question
    {
    public:
        void appendTail(int value) override
        {
            inStack.push(value);
        }

        int deleteHead() override
        {
            if (outStack.empty())
            {
                if (inStack.empty())
                    return -1;
                else
                {
                    while (!inStack.empty())
                    {
                        outStack.push(inStack.top());
                        inStack.pop();
                    }
                }
            }
            const int ans = outStack.top();
            outStack.pop();
            return ans;
        }
    private:
        std::stack<int> inStack, outStack;
    };

    class Practice:public Question
    {
    private:
        std::stack<int> _stack_in;
        std::stack<int> _stack_out;
    public:
        void appendTail(int val)
        {
            _stack_in.push(val);
        }
        int deleteHead()
        {
            if(_stack_out.empty())
            {
                while(!_stack_in.empty())
                {
                    _stack_out.push(_stack_in.top());
                    _stack_in.pop();
                }
            }

            if(_stack_out.empty())
                return -1;

            int pop_val=_stack_out.top();
            _stack_out.pop();
            return pop_val;
        }
    };

    TEST(TwoStackMakeQueueTest, pushAndPop)
    {
        TEST_SOLUTION2(Question, Monitor,Practice, &)
        {
            __slnTestor.setTestTimes(10);

            std::vector<int> nums = TestingUtil::randRangeInts(100, 0, 100);
            std::queue<int> que;

            while(!nums.empty() || !que.empty())
            {
                if(!que.empty() && TestingUtil::randBoolean())
                {
                    int pop_val= solution->deleteHead();
                    EXPECT_EQ(pop_val, que.front());
                    que.pop();
                }
                else if(!nums.empty())
                {
                    que.push(nums.back());
                    solution->appendTail(nums.back());
                    nums.pop_back();
                }
            }
        };
    }
}